package 题目集.动态规划;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/interleaving-string/description/
 */
public class 交错字符串 {

    char[] c1;
    char[] c2;
    char[] c3;
    /**
     * 问题：s1[0~i]和s2[0~j]能否交错组成s3[0~i+j]，求这个集合中的状态。
     *      操作1：最后一个放s1[i]，i<n && s1[i]==s3[i+j]
     *      操作2：最后一个放s2[j], j<m && s2[j]==s3[i+j]
     *      大集合与小集合的关系：dp[i][j]=(dp[i-1][j] && s1[i]==s3[i+j])||(dp[i][j-1] && s2[j]==s3[i+j])
     */
    public boolean isInterleave1(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;

        c1 = s1.toCharArray();
        c2 = s2.toCharArray();
        c3 = s3.toCharArray();
        int n = c1.length;
        int m = c2.length;
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            dp[i][0] = c1[i - 1] == c3[i - 1] && dp[i - 1][0];
            if (!dp[i][0]) break;
        }
        for (int i = 1; i <= m; i++) {
            dp[0][i] = c2[i - 1] == c3[i - 1] && dp[0][i - 1];
            if (!dp[0][i]) break;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = (c1[i - 1] == c3[i + j - 1] && dp[i - 1][j]) || (c2[j - 1] == c3[i + j - 1] && dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;

        c1 = s1.toCharArray();
        c2 = s2.toCharArray();
        c3 = s3.toCharArray();
        int n = c1.length;
        int m = c2.length;
        boolean[]dp = new boolean[m + 1];
        dp[0]= true;

        for (int i = 1; i <= m; i++) {
            dp[i] = c2[i - 1] == c3[i - 1] && dp[i - 1];
            if (!dp[0]) break;
        }

        for (int i = 1; i <= n; i++) {
            dp[0] = c1[i - 1] == c3[i - 1] && dp[0];
            for (int j = 1; j <= m; j++) {
                dp[j] = (c1[i - 1] == c3[i + j - 1] && dp[j]) || (c2[j - 1] == c3[i + j - 1] && dp[j - 1]);
            }
        }
        return dp[m];
    }

    @Test
    public void test() {
        System.out.println(isInterleave("", "", ""));
    }
}
